package twosigma;

import java.math.BigInteger;

public class Solution2 {

	public static void main(String[] args) {
		Solution2 s = new Solution2();
		System.out.println(s.equi(new int[] { -7, 1, 5, 2, -4, 3, 0 }));
		// s.equi(new int[] { -7, 1, 5, 2, -4, 3, 0 });
	}

	public int equi(int[] A) {
		if (A == null || A.length == 0)
			return -1;

		long[] sum = new long[A.length];

		sum[0] = A[0];
		for (int i = 1; i < A.length; ++i) {
			sum[i] = sum[i - 1] + A[i];
		}

		for (int j = 0; j < A.length; ++j) {
			long left = j - 1 < 0 ? 0 : sum[j - 1];
			long right = j + 1 == A.length ? 0 : sum[A.length - 1] - sum[j];

			if (left == right) {
				return j;
			}
		}

		return -1;
	}

	public BigInteger power_fib(int N, int M) {
		return F(BigInteger.valueOf((int) Math.pow(N, M)));
		// return F((int) Math.pow(N, M));// % 10000103;
	}

	public BigInteger F(BigInteger num) {

		if (num.compareTo(BigInteger.valueOf(1)) <= 0)
			return num;

		BigInteger[] arr = new BigInteger[3];

		arr[0] = BigInteger.valueOf(0);
		arr[1] = BigInteger.valueOf(1);

		BigInteger c = BigInteger.valueOf(2);
		while (c.compareTo(num) <= 0) {
			arr[c.mod(BigInteger.valueOf(3)).intValue()] = arr[c.subtract(
					BigInteger.valueOf(1)).mod(BigInteger.valueOf(3))
					.intValue()].add(arr[c.subtract(BigInteger.valueOf(2)).mod(
					BigInteger.valueOf(3)).intValue()]);
			c.add(BigInteger.valueOf(1));
		}

		return arr[num.mod(BigInteger.valueOf(3)).intValue()];
	}
	// public BigInteger F2(BigInteger num) {
	// if (num.compareTo(BigInteger.valueOf(1)) <= 0)
	// return num;
	// return F2(num - 1) + F2(num - 2);
	// }

}
